Сортирање разврставањем

Сваки алгоритам сортирања који сортирање низа врши тако што размењује елементе низа који се сортира (каже се “сортира низ у месту, разменама елемената”) је бар квази-линеарне сложености и захтева у најгорем случају улаза бар \(O(n \log{n})\) операција поређења. Ипак, у неким специфичним ситуацијама (када елементи низа задовољавају неке унапред задате услове) могуће је дизајнирати алгоритме сортирања који су линеарне сложености \(O(n)\). Ти алгоритми се углавном заснивају на пребројавању елемената у низу и често ангажују додатну меморију.

Основни алгоритам соритања линеарне сложености је сортирање пребројавањем (енгл. Counting sort) и он се примењује када знамо да су сви елементи у низу из неког ограниченог опсега вредности и да се по правилу јављају више пута у низу. Основна идеја је да се просто помоћу низа бројача (асоцијативног низа, хеш-таблице) преброји колико се пута у низу јавља сваки од могућих елемената и да се затим низ реконструише на основу те информације (уместо размена, у низ се директно уписује нови садржај).

Други алгоритам је сортирање разврставањем и сортирање вишеструким разврставањем (енгл. Radix sort или Bucket sort). Идеја сортирања разврставањем заснована је на томе да се елементи низа групишу на основу неког критеријума (који је у складу са критеријумом сортирања), а да се затим елементи сваке групе сортирају засебно. Чувени пример је Radix sort код ког се, на пример, низ троцифрених бројева сортира тако што се у првој фази елементи сортирају Counting sort алгоритмом само по цифри јединица, затим истим алгоритмом само по цифри десетица и на крају само по цифри стотина. При томе се води рачуна да се у накнадним фазама редослед еквивалентних елемента не промени. На пример, приликом сортирања по цифри десетица, елементи који имају исту цифру десетица треба да остану у редоследу у ком су били (такво сортирање се назива стабилним). Читаоцу остављамо за вежбу да размисли зашто је овакав поступак коректан, односно зашто се његовом применом добија сортиран низ.

Ово се, наравно, природно уопштава и на вишецифрене бројеве. Такође, основа система записивања која се користи не мора да буде 10 (може се, на пример, користити систем основе 16 или основе 256).